/**
 * @file crop.hh
 * @author Andreas Bok Andersen
 * @brief Implementation of CRoP. Distributes computational load evenly with high probability among processors
 */
//#include "crop.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <tr1/unordered_map>
#include <vector>
#include <iterator>
#include <algorithm>
#include "summary.h"
#include <boost/algorithm/string.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/format.hpp>

#include <boost/random/mersenne_twister.hpp>
#include "boost/random.hpp"
#include <boost/random/uniform_real.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#define CROP_CPP

using namespace std;
using namespace tr1;
using namespace boost;

typedef boost::uniform_01<> NumberDistribution;
typedef boost::mt19937 RandomNumberGenerator;
typedef boost::variate_generator<RandomNumberGenerator&, NumberDistribution> RandGenerator;

typedef unordered_map<unsigned int, unsigned> INT_INT_MAP;
typedef vector<float> FLOAT_VEC;

#ifndef COO_ITEM
struct COO_item {
	COO_item() {
	}
	;
	COO_item(int _i, int _j, float _w) :
			i(_i), j(_j), w(_w) {
	}
	;
	int i, j;
	float w;
};
#define COO_ITEM
#endif

#ifndef DCS_ITEM
typedef struct {
	int i;
	float w;
} DCS_item;
#define DCS_ITEM
#endif

#ifndef COOFORMAT
struct COO_FORMAT {
};
#define COOFORMAT
#endif

#ifndef FORMATDCS
	struct DCS_FORMAT {
	};
#define DCSFORMAT
#endif

struct CropItem {
	int hash, idx;
	float val;

	CropItem(int _hash, int _idx, float _val) {
		hash = _hash;
		idx = _idx;
		val = _val;
	}

	~CropItem() {
	}
};

bool compare(const CropItem& x, const CropItem& y) {
	return x.hash < y.hash;
}

typedef vector<CropItem> CROPITEM_VEC;

RandomNumberGenerator generator;
NumberDistribution distribution;
RandGenerator numberGenerator(generator, distribution);



template<class T>
class Crop {
private:
	int p, rank, size;
	INT_INT_MAP *h1, *h2;
	CROPITEM_VEC *h1val, *h2val;
	T * summary;

	/**
	 * Generates hash value of an row/column index of a matrix.
	 * The hashfunction is using boost uniform_01<> and typedef boost::mt19937 (mersienne twister)
	 * See <a href="http://www.boost.org/doc/libs/1_52_0/doc/html/boost_random/reference.html" target="blank">External file</a>
	 * @param x integer
	 * @param h map of x->hash(x)
	 * @param bit shift for hashfunction making it two-wise independent
	 * @return hash value of x
	 */
	unsigned int val(unsigned int x, INT_INT_MAP *h, int bit) {
		/*	//fprintf(stderr,"%s %d\n", "called val with ", x);
		 ////printf ("h: %d\n", h->size());
		 if ((*h).find(x) == (*h).end()) {
		 //fprintf(stderr,"%s\n", "!has hash(x)");
		 intgen.seed(x + bit);
		 (*h).insert(
		 pair<unsigned int, unsigned int>(x,int(mkrandom(intgen)*p)));
		 //fprintf(stderr,"%s\n", "inserted hash(x)");
		 }
		 //fprintf(stderr,"%s %d\n", "get h[x]", (*h).find(x)->second );
		 return (*h).find(x)->second;*/

		if (h->find(x) == h->end()) {
			generator.seed(x + bit);
			float rand = (float) numberGenerator();
			//cerr << "r: " << rand << endl;
			int _hash = (int) (rand * (float) p);
			h->insert(make_pair<int, int>(x, _hash));
		}
		return h->find(x)->second;
	}


	/**
	 * Multiplication of row from matrix B with assigned col ranges from matrix A
	 * @param col vector of cropitems from matrix A
	 * @param row vector of cropitems from matrix B
	 * @param count array of running sum of items assigned to each processor
	 */
	void do_product(CROPITEM_VEC * col, CROPITEM_VEC * row, int count[]) {
		//fprintf(stderr,"%s\n", "Called do product");
		CROPITEM_VEC::iterator it = row->begin();
		for (; it != row->end(); it++) {
			int a_idx = (p + rank - it->hash) % p;
			CROPITEM_VEC::iterator begin = col->begin() + count[a_idx];
			//fprintf(stderr,"%s\n", "got begin idx of a");
			CROPITEM_VEC::iterator end = col->begin() + count[a_idx + 1];
			//fprintf(stderr,"%s\n", "got end idx of a");
			this->pdist[rank] += distance(begin, end);
			//fprintf(stderr,"rank=%d; ab_range %d, pdist[rank]=%d\n", rank, distance(begin, end), pdist[rank]);
			for (begin; begin != end; begin++) {
				// Add to spacesaving
				this->summary->insert(begin->idx, it->idx,
						it->val * begin->val);
				//this->summary->checksummary();
				//fprintf(stderr,"%s\n", "inserted into summary");
			}
		}
	}

public:
	vector<int> pdist;
	Crop(int rank, int comm_size, int k) :
			rank(rank), p(comm_size) {
		//fprintf(stderr, "INIT CROP: rank: %d, comm_size: %d, k/bufsize %d\n", rank,comm_size, k);

		this->summary = new T(k);
		this->h1 = new INT_INT_MAP();
		this->h2 = new INT_INT_MAP();
		this->pdist.resize(comm_size);
		this->h1val = new CROPITEM_VEC();
		this->h2val = new CROPITEM_VEC();
	}

	~Crop() {
		delete this->h1;
		delete this->summary;
		delete this->h2;
		delete this->h1val;
		delete this->h2val;
	}

	void crop(int * IR, float * NUM, int nnz) {
		//fprintf(stderr,"crop:nnz: %d\n", nnz);
		int counts[p + 1];
		fill_n(counts, p + 1, 0);
		int i;
		for (i = 0; i < nnz; i++) {
			int hash1 = val(IR[i], h1, 0);
			counts[hash1 + 1]++;
			h1val->push_back(CropItem(hash1, IR[i], NUM[i]));
		}

		for (i = 0; i < nnz; i++) {
			h2val->push_back(CropItem(val(IR[i], h2, 1), IR[i], NUM[i]));
		}

		sort(h1val->begin(), h1val->end(), compare);
		//string strcount = "" ;
		for (i = 1; i < p + 1; i++) {
			//strcount += lexical_cast<string>(counts[i]) + ",";
			//fprintf(stderr,"%d, ", counts[i]);
			counts[i] = counts[i - 1] + counts[i];
		}
		//cerr << "counts array" << strcount<<  endl;
		//fprintf(stderr,"%s", "updated count");
		do_product(h1val, h2val, counts);
		h1val->clear();
		h2val->clear();
	}

	/**
	 * @return returns vector of Entry by value
	 */
	ENTRY_VEC get_summary() {
		return this->summary->get_summary();
	}

	/**
	 * Fill entries into array of Entry. Argument is passed by reference
	 * @param entries[] pointer to array of Entry
	 */
	void get_summary(Entry *entries) {
		this->summary->get_summary(entries);
	}

	/**
	 * Fill entries into vector of Entry. Argument is passed by reference
	 * @param entries pointer to vector<Entry>
	 */
	void get_summary(ENTRY_VEC *entries) {
		this->summary->get_summary(entries);
		//fprintf(stderr,"rank %d, %s #%d\n", rank, "crop.GET_vec_summary: ",entries->size());
	}

	/**
	 * @return Returns size of summary
	 */
	int summarysize() {
		return this->summary->summarysize();
	}

	string to_string() {
		return this->summary->to_string();
	}
};
